/*
 * @lc app=leetcode.cn id=67 lang=java
 *
 * [67] 二进制求和
 *
 * https://leetcode-cn.com/problems/add-binary/description/
 *
 * algorithms
 * Easy (51.60%)
 * Likes:    285
 * Dislikes: 0
 * Total Accepted:    56.8K
 * Total Submissions: 109.5K
 * Testcase Example:  '"11"\n"1"'
 *
 * 给定两个二进制字符串，返回他们的和（用二进制表示）。
 *
 * 输入为非空字符串且只包含数字 1 和 0。
 *
 * 示例 1:
 *
 * 输入: a = "11", b = "1"
 * 输出: "100"
 *
 * 示例 2:
 *
 * 输入: a = "1010", b = "1011"
 * 输出: "10101"
 *
 */

// @lc code=start
class Solution {
    public String addBinary(String a, String b) {
        boolean flag = false;
        int i = a.length() - 1, j = b.length() - 1;
        StringBuilder sb = new StringBuilder();
        while(i > -1 && j > -1) {
            char aa = a.charAt(i--), bb = b.charAt(j--);
            int n = aa + bb - '0' - '0' + (flag ? 1: 0) ;
            flag = n > 1;
            sb.insert(0, n%2);
        }
        while(i > -1) {
            char aa = a.charAt(i--);
            int n = aa - '0' + (flag ? 1: 0) ;
            flag = n > 1;
            sb.insert(0, n%2);
        }
        while(j > -1) {
            char aa = b.charAt(j--);
            int n = aa - '0' + (flag ? 1: 0) ;
            flag = n > 1;
            sb.insert(0, n%2);
        }
        if(flag)
            sb.insert(0, '1');
        return sb.toString();
    }
}
// @lc code=end

